알고리즘 프레임워크
수치적 해법은 최소화 수열: 점들의 수열 $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$로, $k \to \infty$일 때 $f(x^{(k)}) \to p^*$가 됩니다. 각 단계에서는 $\Delta x$를 하강 방향으로 하여 $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$로 위치를 갱신합니다.
이 장에서 설명한 방법들은 적절한 시작점 $x^{(0)}$을 필요로 합니다. 시작점은 $\text{dom } f$에 있어야 하며, 추가적으로 하위레벨 집합 $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$이 닫혀 있어야 합니다. 이는 수열이 헤시안이 유용한 정보를 제공하는 잘 정의된 영역 내에 유지되도록 보장합니다.
가장 단순한 방향은 $\Delta x = -\nabla f(x)$. 그러나 효율성을 고려하려면 일반적인 기하학적 구조를 반영해야 하므로 가장 빠른 하강 방향:
- 2차 노름: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$입니다.
- $L_\infty$ 노름: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (좌표 하강법).
이차 모델과 신뢰 영역
뉴턴법은 이차 테일러 근사식을 사용합니다: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ 이 이차식은 $v = \Delta x_{nt}$ (뉴턴 단계)일 때 최소화됩니다. 우리는 신뢰 영역: 집합 $\{v \mid \|v\|_2 \le \gamma\}$. 파라미터 $\gamma$는 이차 모델에 대한 우리의 확신을 반영합니다. 모델이 정확할 경우, 방향은 $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ KKT 시스템에서 구합니다.
- 부적절성 경계: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, $\lambda(x) < 1$일 때 유효합니다.
- 자기일관성의 합: $f_1, f_2$가 자기일관적이라면 $f_1 + f_2$도 자기일관적입니다.
- 헤시안 희소성: 효율성이 향상되는 조건은 헤시안 밴드 구조 조건: $|i-j| > k$인 경우 $\nabla^2 f(x)_{ij} = 0$ 성립할 때입니다.